//快速幂求a^b 复杂度log(b) 
long long Pow(long long base, long long power){
    long long result = 1;
    while(power){
        if(power&1) result *= base
        power >>= 1;
        base *= base;
    }
    return result;
} 

long long fastPower(long long base, long long power, long long mod) {
    long long result = 1;
    while (power > 0) {
        if (power & 1) {//此处等价于if(power%2==1)
            result = result * base % mod;
        }
        power >>= 1;//此处等价于power=power/2
        base = (base * base) % mod;
    }
    return result;
}